package tree.easy;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 剑指 Offer 68 - II. 二叉树的最近公共祖先
 * 236. 二叉树的最近公共祖先
 */
public class lowestCommonAncestorII {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(3, new TreeNode(1), new TreeNode(6)), new TreeNode(8, new TreeNode(7), new TreeNode(9)));
        new lowestCommonAncestorII().lowestCommonAncestor(root, root.left, root.right.right);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        if (leftTree != null && rightTree != null) {
            return root;
        }
        if (leftTree != null) {
            return leftTree;
        }
        return rightTree;
    }
}
